package java.util;

import java.io.IOException;

/**
 * This class provides a red-black tree implementation of the SortedMap
 * interface. Elements in the Map will be sorted by either a user-provided
 * Comparator object, or by the natural ordering of the keys.
 * 
 * The algorithms are adopted from Corman, Leiserson, and Rivest's
 * <i>Introduction to Algorithms.</i> TreeMap guarantees O(log n) insertion and
 * deletion of elements. That being said, there is a large enough constant
 * coefficient in front of that "log n" (overhead involved in keeping the tree
 * balanced), that TreeMap may not be the best choice for small collections. If
 * something is already sorted, you may want to just use a LinkedHashMap to
 * maintain the order while providing O(1) access.
 * 
 * TreeMap is a part of the JDK1.2 Collections API. Null keys are allowed only
 * if a Comparator is used which can deal with them; natural ordering cannot
 * cope with null. Null values are always allowed. Note that the ordering must
 * be <i>consistent with equals</i> to correctly implement the Map interface. If
 * this condition is violated, the map is still well-behaved, but you may have
 * suprising results when comparing it to other maps.
 * <p>
 * 
 * This implementation is not synchronized. If you need to share this between
 * multiple threads, do something like:<br>
 * <code>SortedMap m
 *       = Collections.synchronizedSortedMap(new TreeMap(...));</code>
 * <p>
 * 
 * The iterators are <i>fail-fast</i>, meaning that any structural modification,
 * except for <code>remove()</code> called on the iterator itself, cause the
 * iterator to throw a <code>ConcurrentModificationException</code> rather than
 * exhibit non-deterministic behavior.
 * 
 * @author Jon Zeppieri
 * @author Bryce McKinlay
 * @author Eric Blake (ebb9@email.byu.edu)
 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
 * @see Map
 * @see HashMap
 * @see Hashtable
 * @see LinkedHashMap
 * @see Comparable
 * @see Comparator
 * @see Collection
 * @see Collections#synchronizedSortedMap(SortedMap)
 * @since 1.2
 * @status updated to 1.6
 */
public class TreeMap<K, V> extends AbstractMap<K, V> implements
		NavigableMap<K, V>, Cloneable {
	// Implementation note:
	// A red-black tree is a binary search tree with the additional properties
	// that all paths to a leaf node visit the same number of black nodes,
	// and no red node has red children. To avoid some null-pointer checks,
	// we use the special node nil which is always black, has no relatives,
	// and has key and value of null (but is not equal to a mapping of null).

	/**
	 * Compatible with JDK 1.2.
	 */
	private static final long serialVersionUID = 919286545866124006L;

	/**
	 * Color status of a node. Package visible for use by nested classes.
	 */
	static final int RED = -1, BLACK = 1;

	/**
	 * Sentinal node, used to avoid null checks for corner cases and make the
	 * delete rebalance code simpler. The rebalance code must never assign the
	 * parent, left, or right of nil, but may safely reassign the color to be
	 * black. This object must never be used as a key in a TreeMap, or it will
	 * break bounds checking of a SubMap.
	 */
	static final Node nil = new Node(null, null, BLACK);
	static {
		// Nil is self-referential, so we must initialize it after creation.
		nil.parent = nil;
		nil.left = nil;
		nil.right = nil;
	}

	/**
	 * The root node of this TreeMap.
	 */
	private transient Node root;

	/**
	 * The size of this TreeMap. Package visible for use by nested classes.
	 */
	transient int size;

	/**
	 * The cache for {@link #entrySet()}.
	 */
	private transient Set<Map.Entry<K, V>> entries;

	/**
	 * The cache for {@link #descendingMap()}.
	 */
	private transient NavigableMap<K, V> descendingMap;

	/**
	 * The cache for {@link #navigableKeySet()}.
	 */
	private transient NavigableSet<K> nKeys;

	/**
	 * Counts the number of modifications this TreeMap has undergone, used by
	 * Iterators to know when to throw ConcurrentModificationExceptions. Package
	 * visible for use by nested classes.
	 */
	transient int modCount;

	/**
	 * This TreeMap's comparator, or null for natural ordering. Package visible
	 * for use by nested classes.
	 * 
	 * @serial the comparator ordering this tree, or null
	 */
	final Comparator<? super K> comparator;

	/**
	 * Class to represent an entry in the tree. Holds a single key-value pair,
	 * plus pointers to parent and child nodes.
	 * 
	 * @author Eric Blake (ebb9@email.byu.edu)
	 */
	private static final class Node<K, V> extends AbstractMap.SimpleEntry<K, V> {
		// All fields package visible for use by nested classes.
		/** The color of this node. */
		int color;

		/** The left child node. */
		Node<K, V> left = nil;
		/** The right child node. */
		Node<K, V> right = nil;
		/** The parent node. */
		Node<K, V> parent = nil;

		/**
		 * Simple constructor.
		 * 
		 * @param key
		 *            the key
		 * @param value
		 *            the value
		 */
		Node(K key, V value, int color) {
			super(key, value);
			this.color = color;
		}
	}

	/**
	 * Instantiate a new TreeMap with no elements, using the keys' natural
	 * ordering to sort. All entries in the map must have a key which implements
	 * Comparable, and which are <i>mutually comparable</i>, otherwise map
	 * operations may throw a {@link ClassCastException}. Attempts to use a null
	 * key will throw a {@link NullPointerException}.
	 * 
	 * @see Comparable
	 */
	public TreeMap() {
		this((Comparator) null);
	}

	/**
	 * Instantiate a new TreeMap with no elements, using the provided comparator
	 * to sort. All entries in the map must have keys which are mutually
	 * comparable by the Comparator, otherwise map operations may throw a
	 * {@link ClassCastException}.
	 * 
	 * @param c
	 *            the sort order for the keys of this map, or null for the
	 *            natural order
	 */
	public TreeMap(Comparator<? super K> c) {
		comparator = c;
		fabricateTree(0);
	}

	/**
	 * Instantiate a new TreeMap, initializing it with all of the elements in
	 * the provided Map. The elements will be sorted using the natural ordering
	 * of the keys. This algorithm runs in n*log(n) time. All entries in the map
	 * must have keys which implement Comparable and are mutually comparable,
	 * otherwise map operations may throw a {@link ClassCastException}.
	 * 
	 * @param map
	 *            a Map, whose entries will be put into this TreeMap
	 * @throws ClassCastException
	 *             if the keys in the provided Map are not comparable
	 * @throws NullPointerException
	 *             if map is null
	 * @see Comparable
	 */
	public TreeMap(Map<? extends K, ? extends V> map) {
		this((Comparator) null);
		putAll(map);
	}

	/**
	 * Instantiate a new TreeMap, initializing it with all of the elements in
	 * the provided SortedMap. The elements will be sorted using the same
	 * comparator as in the provided SortedMap. This runs in linear time.
	 * 
	 * @param sm
	 *            a SortedMap, whose entries will be put into this TreeMap
	 * @throws NullPointerException
	 *             if sm is null
	 */
	public TreeMap(SortedMap<K, ? extends V> sm) {
		this(sm.comparator());
		int pos = sm.size();
		Iterator itr = sm.entrySet().iterator();

		fabricateTree(pos);
		Node node = firstNode();

		while (--pos >= 0) {
			Map.Entry me = (Map.Entry) itr.next();
			node.key = me.getKey();
			node.value = me.getValue();
			node = successor(node);
		}
	}

	/**
	 * Clears the Map so it has no keys. This is O(1).
	 */
	public void clear() {
		if (size > 0) {
			modCount++;
			root = nil;
			size = 0;
		}
	}

	/**
	 * Returns a shallow clone of this TreeMap. The Map itself is cloned, but
	 * its contents are not.
	 * 
	 * @return the clone
	 */
	public Object clone() {
		TreeMap copy = null;
		try {
			copy = (TreeMap) super.clone();
		} catch (CloneNotSupportedException x) {
		}
		copy.entries = null;
		copy.fabricateTree(size);

		Node node = firstNode();
		Node cnode = copy.firstNode();

		while (node != nil) {
			cnode.key = node.key;
			cnode.value = node.value;
			node = successor(node);
			cnode = copy.successor(cnode);
		}
		return copy;
	}

	/**
	 * Return the comparator used to sort this map, or null if it is by natural
	 * order.
	 * 
	 * @return the map's comparator
	 */
	public Comparator<? super K> comparator() {
		return comparator;
	}

	/**
	 * Returns true if the map contains a mapping for the given key.
	 * 
	 * @param key
	 *            the key to look for
	 * @return true if the key has a mapping
	 * @throws ClassCastException
	 *             if key is not comparable to map elements
	 * @throws NullPointerException
	 *             if key is null and the comparator is not tolerant of nulls
	 */
	public boolean containsKey(Object key) {
		return getNode((K) key) != nil;
	}

	/**
	 * Returns true if the map contains at least one mapping to the given value.
	 * This requires linear time.
	 * 
	 * @param value
	 *            the value to look for
	 * @return true if the value appears in a mapping
	 */
	public boolean containsValue(Object value) {
		Node node = firstNode();
		while (node != nil) {
			if (equals(value, node.value))
				return true;
			node = successor(node);
		}
		return false;
	}

	/**
	 * Returns a "set view" of this TreeMap's entries. The set is backed by the
	 * TreeMap, so changes in one show up in the other. The set supports element
	 * removal, but not element addition.
	 * <p>
	 * 
	 * Note that the iterators for all three views, from keySet(), entrySet(),
	 * and values(), traverse the TreeMap in sorted sequence.
	 * 
	 * @return a set view of the entries
	 * @see #keySet()
	 * @see #values()
	 * @see Map.Entry
	 */
	public Set<Map.Entry<K, V>> entrySet() {
		if (entries == null)
			// Create an AbstractSet with custom implementations of those
			// methods
			// that can be overriden easily and efficiently.
			entries = new NavigableEntrySet();
		return entries;
	}

	/**
	 * Returns the first (lowest) key in the map.
	 * 
	 * @return the first key
	 * @throws NoSuchElementException
	 *             if the map is empty
	 */
	public K firstKey() {
		if (root == nil)
			throw new NoSuchElementException();
		return firstNode().key;
	}

	/**
	 * Return the value in this TreeMap associated with the supplied key, or
	 * <code>null</code> if the key maps to nothing. NOTE: Since the value could
	 * also be null, you must use containsKey to see if this key actually maps
	 * to something.
	 * 
	 * @param key
	 *            the key for which to fetch an associated value
	 * @return what the key maps to, if present
	 * @throws ClassCastException
	 *             if key is not comparable to elements in the map
	 * @throws NullPointerException
	 *             if key is null but the comparator does not tolerate nulls
	 * @see #put(Object, Object)
	 * @see #containsKey(Object)
	 */
	public V get(Object key) {
		// Exploit fact that nil.value == null.
		return getNode((K) key).value;
	}

	/**
	 * Returns a view of this Map including all entries with keys less than
	 * <code>toKey</code>. The returned map is backed by the original, so
	 * changes in one appear in the other. The submap will throw an
	 * {@link IllegalArgumentException} for any attempt to access or add an
	 * element beyond the specified cutoff. The returned map does not include
	 * the endpoint; if you want inclusion, pass the successor element or call
	 * <code>headMap(toKey, true)</code>. This is equivalent to calling
	 * <code>headMap(toKey, false)</code>.
	 * 
	 * @param toKey
	 *            the (exclusive) cutoff point
	 * @return a view of the map less than the cutoff
	 * @throws ClassCastException
	 *             if <code>toKey</code> is not compatible with the comparator
	 *             (or is not Comparable, for natural ordering)
	 * @throws NullPointerException
	 *             if toKey is null, but the comparator does not tolerate null
	 *             elements
	 */
	public SortedMap<K, V> headMap(K toKey) {
		return headMap(toKey, false);
	}

	/**
	 * Returns a view of this Map including all entries with keys less than (or
	 * equal to, if <code>inclusive</code> is true) <code>toKey</code>. The
	 * returned map is backed by the original, so changes in one appear in the
	 * other. The submap will throw an {@link IllegalArgumentException} for any
	 * attempt to access or add an element beyond the specified cutoff.
	 * 
	 * @param toKey
	 *            the cutoff point
	 * @param inclusive
	 *            true if the cutoff point should be included.
	 * @return a view of the map less than (or equal to, if
	 *         <code>inclusive</code> is true) the cutoff.
	 * @throws ClassCastException
	 *             if <code>toKey</code> is not compatible with the comparator
	 *             (or is not Comparable, for natural ordering)
	 * @throws NullPointerException
	 *             if toKey is null, but the comparator does not tolerate null
	 *             elements
	 */
	public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
		return new SubMap((K) (Object) nil,
				inclusive ? successor(getNode(toKey)).key : toKey);
	}

	/**
	 * Returns a "set view" of this TreeMap's keys. The set is backed by the
	 * TreeMap, so changes in one show up in the other. The set supports element
	 * removal, but not element addition.
	 * 
	 * @return a set view of the keys
	 * @see #values()
	 * @see #entrySet()
	 */
	public Set<K> keySet() {
		if (keys == null)
			// Create an AbstractSet with custom implementations of those
			// methods
			// that can be overriden easily and efficiently.
			keys = new KeySet();
		return keys;
	}

	/**
	 * Returns the last (highest) key in the map.
	 * 
	 * @return the last key
	 * @throws NoSuchElementException
	 *             if the map is empty
	 */
	public K lastKey() {
		if (root == nil)
			throw new NoSuchElementException("empty");
		return lastNode().key;
	}

	/**
	 * Puts the supplied value into the Map, mapped by the supplied key. The
	 * value may be retrieved by any object which <code>equals()</code> this
	 * key. NOTE: Since the prior value could also be null, you must first use
	 * containsKey if you want to see if you are replacing the key's mapping.
	 * 
	 * @param key
	 *            the key used to locate the value
	 * @param value
	 *            the value to be stored in the Map
	 * @return the prior mapping of the key, or null if there was none
	 * @throws ClassCastException
	 *             if key is not comparable to current map keys
	 * @throws NullPointerException
	 *             if key is null, but the comparator does not tolerate nulls
	 * @see #get(Object)
	 * @see Object#equals(Object)
	 */
	public V put(K key, V value) {
		Node<K, V> current = root;
		Node<K, V> parent = nil;
		int comparison = 0;

		// Find new node's parent.
		while (current != nil) {
			parent = current;
			comparison = compare(key, current.key);
			if (comparison > 0)
				current = current.right;
			else if (comparison < 0)
				current = current.left;
			else
				// Key already in tree.
				return current.setValue(value);
		}

		// Set up new node.
		Node n = new Node(key, value, RED);
		n.parent = parent;

		// Insert node in tree.
		modCount++;
		size++;
		if (parent == nil) {
			// Special case inserting into an empty tree.
			root = n;
			return null;
		}
		if (comparison > 0)
			parent.right = n;
		else
			parent.left = n;

		// Rebalance after insert.
		insertFixup(n);
		return null;
	}

	/**
	 * Copies all elements of the given map into this TreeMap. If this map
	 * already has a mapping for a key, the new mapping replaces the current
	 * one.
	 * 
	 * @param m
	 *            the map to be added
	 * @throws ClassCastException
	 *             if a key in m is not comparable with keys in the map
	 * @throws NullPointerException
	 *             if a key in m is null, and the comparator does not tolerate
	 *             nulls
	 */
	public void putAll(Map<? extends K, ? extends V> m) {
		Iterator itr = m.entrySet().iterator();
		int pos = m.size();
		while (--pos >= 0) {
			Map.Entry<K, V> e = (Map.Entry<K, V>) itr.next();
			put(e.getKey(), e.getValue());
		}
	}

	/**
	 * Removes from the TreeMap and returns the value which is mapped by the
	 * supplied key. If the key maps to nothing, then the TreeMap remains
	 * unchanged, and <code>null</code> is returned. NOTE: Since the value could
	 * also be null, you must use containsKey to see if you are actually
	 * removing a mapping.
	 * 
	 * @param key
	 *            the key used to locate the value to remove
	 * @return whatever the key mapped to, if present
	 * @throws ClassCastException
	 *             if key is not comparable to current map keys
	 * @throws NullPointerException
	 *             if key is null, but the comparator does not tolerate nulls
	 */
	public V remove(Object key) {
		Node<K, V> n = getNode((K) key);
		if (n == nil)
			return null;
		// Note: removeNode can alter the contents of n, so save value now.
		V result = n.value;
		removeNode(n);
		return result;
	}

	/**
	 * Returns the number of key-value mappings currently in this Map.
	 * 
	 * @return the size
	 */
	public int size() {
		return size;
	}

	/**
	 * Returns a view of this Map including all entries with keys greater or
	 * equal to <code>fromKey</code> and less than <code>toKey</code> (a
	 * half-open interval). The returned map is backed by the original, so
	 * changes in one appear in the other. The submap will throw an
	 * {@link IllegalArgumentException} for any attempt to access or add an
	 * element beyond the specified cutoffs. The returned map includes the low
	 * endpoint but not the high; if you want to reverse this behavior on either
	 * end, pass in the successor element or call
	 * {@link #subMap(K,boolean,K,boolean)}. This call is equivalent to
	 * <code>subMap(fromKey, true, toKey, false)</code>.
	 * 
	 * @param fromKey
	 *            the (inclusive) low cutoff point
	 * @param toKey
	 *            the (exclusive) high cutoff point
	 * @return a view of the map between the cutoffs
	 * @throws ClassCastException
	 *             if either cutoff is not compatible with the comparator (or is
	 *             not Comparable, for natural ordering)
	 * @throws NullPointerException
	 *             if fromKey or toKey is null, but the comparator does not
	 *             tolerate null elements
	 * @throws IllegalArgumentException
	 *             if fromKey is greater than toKey
	 */
	public SortedMap<K, V> subMap(K fromKey, K toKey) {
		return subMap(fromKey, true, toKey, false);
	}

	/**
	 * Returns a view of this Map including all entries with keys greater (or
	 * equal to, if <code>fromInclusive</code> is true) <code>fromKey</code> and
	 * less than (or equal to, if <code>toInclusive</code> is true)
	 * <code>toKey</code>. The returned map is backed by the original, so
	 * changes in one appear in the other. The submap will throw an
	 * {@link IllegalArgumentException} for any attempt to access or add an
	 * element beyond the specified cutoffs.
	 * 
	 * @param fromKey
	 *            the low cutoff point
	 * @param fromInclusive
	 *            true if the low cutoff point should be included.
	 * @param toKey
	 *            the high cutoff point
	 * @param toInclusive
	 *            true if the high cutoff point should be included.
	 * @return a view of the map for the specified range.
	 * @throws ClassCastException
	 *             if either cutoff is not compatible with the comparator (or is
	 *             not Comparable, for natural ordering)
	 * @throws NullPointerException
	 *             if fromKey or toKey is null, but the comparator does not
	 *             tolerate null elements
	 * @throws IllegalArgumentException
	 *             if fromKey is greater than toKey
	 */
	public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey,
			boolean toInclusive) {
		return new SubMap(fromInclusive ? fromKey
				: successor(getNode(fromKey)).key,
				toInclusive ? successor(getNode(toKey)).key : toKey);
	}

	/**
	 * Returns a view of this Map including all entries with keys greater or
	 * equal to <code>fromKey</code>. The returned map is backed by the
	 * original, so changes in one appear in the other. The submap will throw an
	 * {@link IllegalArgumentException} for any attempt to access or add an
	 * element beyond the specified cutoff. The returned map includes the
	 * endpoint; if you want to exclude it, pass in the successor element. This
	 * is equivalent to calling <code>tailMap(fromKey, true)</code>.
	 * 
	 * @param fromKey
	 *            the (inclusive) low cutoff point
	 * @return a view of the map above the cutoff
	 * @throws ClassCastException
	 *             if <code>fromKey</code> is not compatible with the comparator
	 *             (or is not Comparable, for natural ordering)
	 * @throws NullPointerException
	 *             if fromKey is null, but the comparator does not tolerate null
	 *             elements
	 */
	public SortedMap<K, V> tailMap(K fromKey) {
		return tailMap(fromKey, true);
	}

	/**
	 * Returns a view of this Map including all entries with keys greater or
	 * equal to <code>fromKey</code>. The returned map is backed by the
	 * original, so changes in one appear in the other. The submap will throw an
	 * {@link IllegalArgumentException} for any attempt to access or add an
	 * element beyond the specified cutoff. The returned map includes the
	 * endpoint; if you want to exclude it, pass in the successor element.
	 * 
	 * @param fromKey
	 *            the low cutoff point
	 * @param inclusive
	 *            true if the cutoff point should be included.
	 * @return a view of the map above the cutoff
	 * @throws ClassCastException
	 *             if <code>fromKey</code> is not compatible with the comparator
	 *             (or is not Comparable, for natural ordering)
	 * @throws NullPointerException
	 *             if fromKey is null, but the comparator does not tolerate null
	 *             elements
	 */
	public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
		return new SubMap(
				inclusive ? fromKey : successor(getNode(fromKey)).key,
				(K) (Object) nil);
	}

	/**
	 * Returns a "collection view" (or "bag view") of this TreeMap's values. The
	 * collection is backed by the TreeMap, so changes in one show up in the
	 * other. The collection supports element removal, but not element addition.
	 * 
	 * @return a bag view of the values
	 * @see #keySet()
	 * @see #entrySet()
	 */
	public Collection<V> values() {
		if (values == null)
			// We don't bother overriding many of the optional methods, as doing
			// so
			// wouldn't provide any significant performance advantage.
			values = new AbstractCollection<V>() {
				public int size() {
					return size;
				}

				public Iterator<V> iterator() {
					return new TreeIterator(VALUES);
				}

				public void clear() {
					TreeMap.this.clear();
				}
			};
		return values;
	}

	/**
	 * Compares two elements by the set comparator, or by natural ordering.
	 * Package visible for use by nested classes.
	 * 
	 * @param o1
	 *            the first object
	 * @param o2
	 *            the second object
	 * @throws ClassCastException
	 *             if o1 and o2 are not mutually comparable, or are not
	 *             Comparable with natural ordering
	 * @throws NullPointerException
	 *             if o1 or o2 is null with natural ordering
	 */
	final int compare(K o1, K o2) {
		return (comparator == null ? ((Comparable) o1).compareTo(o2)
				: comparator.compare(o1, o2));
	}

	/**
	 * Maintain red-black balance after deleting a node.
	 * 
	 * @param node
	 *            the child of the node just deleted, possibly nil
	 * @param parent
	 *            the parent of the node just deleted, never nil
	 */
	private void deleteFixup(Node<K, V> node, Node<K, V> parent) {
		// if (parent == nil)
		// throw new InternalError();
		// If a black node has been removed, we need to rebalance to avoid
		// violating the "same number of black nodes on any path" rule. If
		// node is red, we can simply recolor it black and all is well.
		while (node != root && node.color == BLACK) {
			if (node == parent.left) {
				// Rebalance left side.
				Node<K, V> sibling = parent.right;
				// if (sibling == nil)
				// throw new InternalError();
				if (sibling.color == RED) {
					// Case 1: Sibling is red.
					// Recolor sibling and parent, and rotate parent left.
					sibling.color = BLACK;
					parent.color = RED;
					rotateLeft(parent);
					sibling = parent.right;
				}

				if (sibling.left.color == BLACK && sibling.right.color == BLACK) {
					// Case 2: Sibling has no red children.
					// Recolor sibling, and move to parent.
					sibling.color = RED;
					node = parent;
					parent = parent.parent;
				} else {
					if (sibling.right.color == BLACK) {
						// Case 3: Sibling has red left child.
						// Recolor sibling and left child, rotate sibling right.
						sibling.left.color = BLACK;
						sibling.color = RED;
						rotateRight(sibling);
						sibling = parent.right;
					}
					// Case 4: Sibling has red right child. Recolor sibling,
					// right child, and parent, and rotate parent left.
					sibling.color = parent.color;
					parent.color = BLACK;
					sibling.right.color = BLACK;
					rotateLeft(parent);
					node = root; // Finished.
				}
			} else {
				// Symmetric "mirror" of left-side case.
				Node<K, V> sibling = parent.left;
				// if (sibling == nil)
				// throw new InternalError();
				if (sibling.color == RED) {
					// Case 1: Sibling is red.
					// Recolor sibling and parent, and rotate parent right.
					sibling.color = BLACK;
					parent.color = RED;
					rotateRight(parent);
					sibling = parent.left;
				}

				if (sibling.right.color == BLACK && sibling.left.color == BLACK) {
					// Case 2: Sibling has no red children.
					// Recolor sibling, and move to parent.
					sibling.color = RED;
					node = parent;
					parent = parent.parent;
				} else {
					if (sibling.left.color == BLACK) {
						// Case 3: Sibling has red right child.
						// Recolor sibling and right child, rotate sibling left.
						sibling.right.color = BLACK;
						sibling.color = RED;
						rotateLeft(sibling);
						sibling = parent.left;
					}
					// Case 4: Sibling has red left child. Recolor sibling,
					// left child, and parent, and rotate parent right.
					sibling.color = parent.color;
					parent.color = BLACK;
					sibling.left.color = BLACK;
					rotateRight(parent);
					node = root; // Finished.
				}
			}
		}
		node.color = BLACK;
	}

	/**
	 * Construct a perfectly balanced tree consisting of n "blank" nodes. This
	 * permits a tree to be generated from pre-sorted input in linear time.
	 * 
	 * @param count
	 *            the number of blank nodes, non-negative
	 */
	private void fabricateTree(final int count) {
		if (count == 0) {
			root = nil;
			size = 0;
			return;
		}

		// We color every row of nodes black, except for the overflow nodes.
		// I believe that this is the optimal arrangement. We construct the tree
		// in place by temporarily linking each node to the next node in the
		// row,
		// then updating those links to the children when working on the next
		// row.

		// Make the root node.
		root = new Node(null, null, BLACK);
		size = count;
		Node row = root;
		int rowsize;

		// Fill each row that is completely full of nodes.
		for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1) {
			Node parent = row;
			Node last = null;
			for (int i = 0; i < rowsize; i += 2) {
				Node left = new Node(null, null, BLACK);
				Node right = new Node(null, null, BLACK);
				left.parent = parent;
				left.right = right;
				right.parent = parent;
				parent.left = left;
				Node next = parent.right;
				parent.right = right;
				parent = next;
				if (last != null)
					last.right = left;
				last = right;
			}
			row = row.left;
		}

		// Now do the partial final row in red.
		int overflow = count - rowsize;
		Node parent = row;
		int i;
		for (i = 0; i < overflow; i += 2) {
			Node left = new Node(null, null, RED);
			Node right = new Node(null, null, RED);
			left.parent = parent;
			right.parent = parent;
			parent.left = left;
			Node next = parent.right;
			parent.right = right;
			parent = next;
		}
		// Add a lone left node if necessary.
		if (i - overflow == 0) {
			Node left = new Node(null, null, RED);
			left.parent = parent;
			parent.left = left;
			parent = parent.right;
			left.parent.right = nil;
		}
		// Unlink the remaining nodes of the previous row.
		while (parent != nil) {
			Node next = parent.right;
			parent.right = nil;
			parent = next;
		}
	}

	/**
	 * Returns the first sorted node in the map, or nil if empty. Package
	 * visible for use by nested classes.
	 * 
	 * @return the first node
	 */
	final Node<K, V> firstNode() {
		// Exploit fact that nil.left == nil.
		Node node = root;
		while (node.left != nil)
			node = node.left;
		return node;
	}

	/**
	 * Return the TreeMap.Node associated with key, or the nil node if no such
	 * node exists in the tree. Package visible for use by nested classes.
	 * 
	 * @param key
	 *            the key to search for
	 * @return the node where the key is found, or nil
	 */
	final Node<K, V> getNode(K key) {
		Node<K, V> current = root;
		while (current != nil) {
			int comparison = compare(key, current.key);
			if (comparison > 0)
				current = current.right;
			else if (comparison < 0)
				current = current.left;
			else
				return current;
		}
		return current;
	}

	/**
	 * Find the "highest" node which is &lt; key. If key is nil, return last
	 * node. Package visible for use by nested classes.
	 * 
	 * @param key
	 *            the upper bound, exclusive
	 * @return the previous node
	 */
	final Node<K, V> highestLessThan(K key) {
		return highestLessThan(key, false);
	}

	/**
	 * Find the "highest" node which is &lt; (or equal to, if <code>equal</code>
	 * is true) key. If key is nil, return last node. Package visible for use by
	 * nested classes.
	 * 
	 * @param key
	 *            the upper bound, exclusive
	 * @param equal
	 *            true if the key should be returned if found.
	 * @return the previous node
	 */
	final Node<K, V> highestLessThan(K key, boolean equal) {
		if (key == nil)
			return lastNode();

		Node<K, V> last = nil;
		Node<K, V> current = root;
		int comparison = 0;

		while (current != nil) {
			last = current;
			comparison = compare(key, current.key);
			if (comparison > 0)
				current = current.right;
			else if (comparison < 0)
				current = current.left;
			else
				// Exact match.
				return (equal ? last : predecessor(last));
		}
		return comparison < 0 ? predecessor(last) : last;
	}

	/**
	 * Maintain red-black balance after inserting a new node.
	 * 
	 * @param n
	 *            the newly inserted node
	 */
	private void insertFixup(Node<K, V> n) {
		// Only need to rebalance when parent is a RED node, and while at least
		// 2 levels deep into the tree (ie: node has a grandparent). Remember
		// that nil.color == BLACK.
		while (n.parent.color == RED && n.parent.parent != nil) {
			if (n.parent == n.parent.parent.left) {
				Node uncle = n.parent.parent.right;
				// Uncle may be nil, in which case it is BLACK.
				if (uncle.color == RED) {
					// Case 1. Uncle is RED: Change colors of parent, uncle,
					// and grandparent, and move n to grandparent.
					n.parent.color = BLACK;
					uncle.color = BLACK;
					uncle.parent.color = RED;
					n = uncle.parent;
				} else {
					if (n == n.parent.right) {
						// Case 2. Uncle is BLACK and x is right child.
						// Move n to parent, and rotate n left.
						n = n.parent;
						rotateLeft(n);
					}
					// Case 3. Uncle is BLACK and x is left child.
					// Recolor parent, grandparent, and rotate grandparent
					// right.
					n.parent.color = BLACK;
					n.parent.parent.color = RED;
					rotateRight(n.parent.parent);
				}
			} else {
				// Mirror image of above code.
				Node uncle = n.parent.parent.left;
				// Uncle may be nil, in which case it is BLACK.
				if (uncle.color == RED) {
					// Case 1. Uncle is RED: Change colors of parent, uncle,
					// and grandparent, and move n to grandparent.
					n.parent.color = BLACK;
					uncle.color = BLACK;
					uncle.parent.color = RED;
					n = uncle.parent;
				} else {
					if (n == n.parent.left) {
						// Case 2. Uncle is BLACK and x is left child.
						// Move n to parent, and rotate n right.
						n = n.parent;
						rotateRight(n);
					}
					// Case 3. Uncle is BLACK and x is right child.
					// Recolor parent, grandparent, and rotate grandparent left.
					n.parent.color = BLACK;
					n.parent.parent.color = RED;
					rotateLeft(n.parent.parent);
				}
			}
		}
		root.color = BLACK;
	}

	/**
	 * Returns the last sorted node in the map, or nil if empty.
	 * 
	 * @return the last node
	 */
	private Node<K, V> lastNode() {
		// Exploit fact that nil.right == nil.
		Node node = root;
		while (node.right != nil)
			node = node.right;
		return node;
	}

	/**
	 * Find the "lowest" node which is &gt;= key. If key is nil, return either
	 * nil or the first node, depending on the parameter first. Package visible
	 * for use by nested classes.
	 * 
	 * @param key
	 *            the lower bound, inclusive
	 * @param first
	 *            true to return the first element instead of nil for nil key
	 * @return the next node
	 */
	final Node<K, V> lowestGreaterThan(K key, boolean first) {
		return lowestGreaterThan(key, first, true);
	}

	/**
	 * Find the "lowest" node which is &gt; (or equal to, if <code>equal</code>
	 * is true) key. If key is nil, return either nil or the first node,
	 * depending on the parameter first. Package visible for use by nested
	 * classes.
	 * 
	 * @param key
	 *            the lower bound, inclusive
	 * @param first
	 *            true to return the first element instead of nil for nil key
	 * @param equal
	 *            true if the key should be returned if found.
	 * @return the next node
	 */
	final Node<K, V> lowestGreaterThan(K key, boolean first, boolean equal) {
		if (key == nil)
			return first ? firstNode() : nil;

		Node<K, V> last = nil;
		Node<K, V> current = root;
		int comparison = 0;

		while (current != nil) {
			last = current;
			comparison = compare(key, current.key);
			if (comparison > 0)
				current = current.right;
			else if (comparison < 0)
				current = current.left;
			else
				return (equal ? current : successor(current));
		}
		return comparison > 0 ? successor(last) : last;
	}

	/**
	 * Return the node preceding the given one, or nil if there isn't one.
	 * 
	 * @param node
	 *            the current node, not nil
	 * @return the prior node in sorted order
	 */
	private Node<K, V> predecessor(Node<K, V> node) {
		if (node.left != nil) {
			node = node.left;
			while (node.right != nil)
				node = node.right;
			return node;
		}

		Node parent = node.parent;
		// Exploit fact that nil.left == nil and node is non-nil.
		while (node == parent.left) {
			node = parent;
			parent = node.parent;
		}
		return parent;
	}

	/**
	 * Construct a tree from sorted keys in linear time, with values of "".
	 * Package visible for use by TreeSet, which uses a value type of String.
	 * 
	 * @param keys
	 *            the iterator over the sorted keys
	 * @param count
	 *            the number of nodes to insert
	 * @see TreeSet#TreeSet(SortedSet)
	 */
	final void putKeysLinear(Iterator<K> keys, int count) {
		fabricateTree(count);
		Node<K, V> node = firstNode();

		while (--count >= 0) {
			node.key = keys.next();
			node.value = (V) "";
			node = successor(node);
		}
	}

	/**
	 * Remove node from tree. This will increment modCount and decrement size.
	 * Node must exist in the tree. Package visible for use by nested classes.
	 * 
	 * @param node
	 *            the node to remove
	 */
	final void removeNode(Node<K, V> node) {
		Node<K, V> splice;
		Node<K, V> child;

		modCount++;
		size--;

		// Find splice, the node at the position to actually remove from the
		// tree.
		if (node.left == nil) {
			// Node to be deleted has 0 or 1 children.
			splice = node;
			child = node.right;
		} else if (node.right == nil) {
			// Node to be deleted has 1 child.
			splice = node;
			child = node.left;
		} else {
			// Node has 2 children. Splice is node's predecessor, and we swap
			// its contents into node.
			splice = node.left;
			while (splice.right != nil)
				splice = splice.right;
			child = splice.left;
			node.key = splice.key;
			node.value = splice.value;
		}

		// Unlink splice from the tree.
		Node parent = splice.parent;
		if (child != nil)
			child.parent = parent;
		if (parent == nil) {
			// Special case for 0 or 1 node remaining.
			root = child;
			return;
		}
		if (splice == parent.left)
			parent.left = child;
		else
			parent.right = child;

		if (splice.color == BLACK)
			deleteFixup(child, parent);
	}

	/**
	 * Rotate node n to the left.
	 * 
	 * @param node
	 *            the node to rotate
	 */
	private void rotateLeft(Node<K, V> node) {
		Node child = node.right;
		// if (node == nil || child == nil)
		// throw new InternalError();

		// Establish node.right link.
		node.right = child.left;
		if (child.left != nil)
			child.left.parent = node;

		// Establish child->parent link.
		child.parent = node.parent;
		if (node.parent != nil) {
			if (node == node.parent.left)
				node.parent.left = child;
			else
				node.parent.right = child;
		} else
			root = child;

		// Link n and child.
		child.left = node;
		node.parent = child;
	}

	/**
	 * Rotate node n to the right.
	 * 
	 * @param node
	 *            the node to rotate
	 */
	private void rotateRight(Node<K, V> node) {
		Node child = node.left;
		// if (node == nil || child == nil)
		// throw new InternalError();

		// Establish node.left link.
		node.left = child.right;
		if (child.right != nil)
			child.right.parent = node;

		// Establish child->parent link.
		child.parent = node.parent;
		if (node.parent != nil) {
			if (node == node.parent.right)
				node.parent.right = child;
			else
				node.parent.left = child;
		} else
			root = child;

		// Link n and child.
		child.right = node;
		node.parent = child;
	}

	/**
	 * Return the node following the given one, or nil if there isn't one.
	 * Package visible for use by nested classes.
	 * 
	 * @param node
	 *            the current node, not nil
	 * @return the next node in sorted order
	 */
	final Node<K, V> successor(Node<K, V> node) {
		if (node.right != nil) {
			node = node.right;
			while (node.left != nil)
				node = node.left;
			return node;
		}

		Node<K, V> parent = node.parent;
		// Exploit fact that nil.right == nil and node is non-nil.
		while (node == parent.right) {
			node = parent;
			parent = parent.parent;
		}
		return parent;
	}

	/**
	 * Iterate over TreeMap's entries. This implementation is parameterized to
	 * give a sequential view of keys, values, or entries.
	 * 
	 * @author Eric Blake (ebb9@email.byu.edu)
	 */
	private final class TreeIterator implements Iterator {
		/**
		 * The type of this Iterator: {@link #KEYS}, {@link #VALUES}, or
		 * {@link #ENTRIES}.
		 */
		private final int type;
		/** The number of modifications to the backing Map that we know about. */
		private int knownMod = modCount;
		/** The last Entry returned by a next() call. */
		private Node last;
		/** The next entry that should be returned by next(). */
		private Node next;
		/**
		 * The last node visible to this iterator. This is used when iterating
		 * on a SubMap.
		 */
		private final Node max;

		/**
		 * Construct a new TreeIterator with the supplied type.
		 * 
		 * @param type
		 *            {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
		 */
		TreeIterator(int type) {
			this(type, firstNode(), nil);
		}

		/**
		 * Construct a new TreeIterator with the supplied type. Iteration will
		 * be from "first" (inclusive) to "max" (exclusive).
		 * 
		 * @param type
		 *            {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
		 * @param first
		 *            where to start iteration, nil for empty iterator
		 * @param max
		 *            the cutoff for iteration, nil for all remaining nodes
		 */
		TreeIterator(int type, Node first, Node max) {
			this.type = type;
			this.next = first;
			this.max = max;
		}

		/**
		 * Returns true if the Iterator has more elements.
		 * 
		 * @return true if there are more elements
		 */
		public boolean hasNext() {
			return next != max;
		}

		/**
		 * Returns the next element in the Iterator's sequential view.
		 * 
		 * @return the next element
		 * @throws ConcurrentModificationException
		 *             if the TreeMap was modified
		 * @throws NoSuchElementException
		 *             if there is none
		 */
		public Object next() {
			if (knownMod != modCount)
				throw new ConcurrentModificationException();
			if (next == max)
				throw new NoSuchElementException();
			last = next;
			next = successor(last);

			if (type == VALUES)
				return last.value;
			else if (type == KEYS)
				return last.key;
			return last;
		}

		/**
		 * Removes from the backing TreeMap the last element which was fetched
		 * with the <code>next()</code> method.
		 * 
		 * @throws ConcurrentModificationException
		 *             if the TreeMap was modified
		 * @throws IllegalStateException
		 *             if called when there is no last element
		 */
		public void remove() {
			if (last == null)
				throw new IllegalStateException();
			if (knownMod != modCount)
				throw new ConcurrentModificationException();

			removeNode(last);
			last = null;
			knownMod++;
		}
	} // class TreeIterator

	/**
	 * Implementation of {@link #subMap(Object, Object)} and other map ranges.
	 * This class provides a view of a portion of the original backing map, and
	 * throws {@link IllegalArgumentException} for attempts to access beyond
	 * that range.
	 * 
	 * @author Eric Blake (ebb9@email.byu.edu)
	 */
	private final class SubMap extends AbstractMap<K, V> implements
			NavigableMap<K, V> {
		/**
		 * The lower range of this view, inclusive, or nil for unbounded.
		 * Package visible for use by nested classes.
		 */
		final K minKey;

		/**
		 * The upper range of this view, exclusive, or nil for unbounded.
		 * Package visible for use by nested classes.
		 */
		final K maxKey;

		/**
		 * The cache for {@link #entrySet()}.
		 */
		private Set<Map.Entry<K, V>> entries;

		/**
		 * The cache for {@link #descendingMap()}.
		 */
		private NavigableMap<K, V> descendingMap;

		/**
		 * The cache for {@link #navigableKeySet()}.
		 */
		private NavigableSet<K> nKeys;

		/**
		 * Create a SubMap representing the elements between minKey (inclusive)
		 * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound
		 * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).
		 * 
		 * @param minKey
		 *            the lower bound
		 * @param maxKey
		 *            the upper bound
		 * @throws IllegalArgumentException
		 *             if minKey &gt; maxKey
		 */
		SubMap(K minKey, K maxKey) {
			if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
				throw new IllegalArgumentException("fromKey > toKey");
			this.minKey = minKey;
			this.maxKey = maxKey;
		}

		/**
		 * Check if "key" is in within the range bounds for this SubMap. The
		 * lower ("from") SubMap range is inclusive, and the upper ("to") bound
		 * is exclusive. Package visible for use by nested classes.
		 * 
		 * @param key
		 *            the key to check
		 * @return true if the key is in range
		 */
		boolean keyInRange(K key) {
			return ((minKey == nil || compare(key, minKey) >= 0) && (maxKey == nil || compare(
					key, maxKey) < 0));
		}

		public Entry<K, V> ceilingEntry(K key) {
			Entry<K, V> n = TreeMap.this.ceilingEntry(key);
			if (n != null && keyInRange(n.getKey()))
				return n;
			return null;
		}

		public K ceilingKey(K key) {
			K found = TreeMap.this.ceilingKey(key);
			if (keyInRange(found))
				return found;
			else
				return null;
		}

		public NavigableSet<K> descendingKeySet() {
			return descendingMap().navigableKeySet();
		}

		public NavigableMap<K, V> descendingMap() {
			if (descendingMap == null)
				descendingMap = new DescendingMap(this);
			return descendingMap;
		}

		public void clear() {
			Node next = lowestGreaterThan(minKey, true);
			Node max = lowestGreaterThan(maxKey, false);
			while (next != max) {
				Node current = next;
				next = successor(current);
				removeNode(current);
			}
		}

		public Comparator<? super K> comparator() {
			return comparator;
		}

		public boolean containsKey(Object key) {
			return keyInRange((K) key) && TreeMap.this.containsKey(key);
		}

		public boolean containsValue(Object value) {
			Node node = lowestGreaterThan(minKey, true);
			Node max = lowestGreaterThan(maxKey, false);
			while (node != max) {
				if (equals(value, node.getValue()))
					return true;
				node = successor(node);
			}
			return false;
		}

		public Set<Map.Entry<K, V>> entrySet() {
			if (entries == null)
				// Create an AbstractSet with custom implementations of those
				// methods
				// that can be overriden easily and efficiently.
				entries = new SubMap.NavigableEntrySet();
			return entries;
		}

		public Entry<K, V> firstEntry() {
			Node<K, V> node = lowestGreaterThan(minKey, true);
			if (node == nil || !keyInRange(node.key))
				return null;
			return node;
		}

		public K firstKey() {
			Entry<K, V> e = firstEntry();
			if (e == null)
				throw new NoSuchElementException();
			return e.getKey();
		}

		public Entry<K, V> floorEntry(K key) {
			Entry<K, V> n = TreeMap.this.floorEntry(key);
			if (n != null && keyInRange(n.getKey()))
				return n;
			return null;
		}

		public K floorKey(K key) {
			K found = TreeMap.this.floorKey(key);
			if (keyInRange(found))
				return found;
			else
				return null;
		}

		public V get(Object key) {
			if (keyInRange((K) key))
				return TreeMap.this.get(key);
			return null;
		}

		public SortedMap<K, V> headMap(K toKey) {
			return headMap(toKey, false);
		}

		public NavigableMap<K, V> headMap(K toKey, boolean inclusive) {
			if (!keyInRange(toKey))
				throw new IllegalArgumentException("Key outside submap range");
			return new SubMap(minKey,
					(inclusive ? successor(getNode(toKey)).key : toKey));
		}

		public Set<K> keySet() {
			if (this.keys == null)
				// Create an AbstractSet with custom implementations of those
				// methods
				// that can be overriden easily and efficiently.
				this.keys = new SubMap.KeySet();
			return this.keys;
		}

		public Entry<K, V> higherEntry(K key) {
			Entry<K, V> n = TreeMap.this.higherEntry(key);
			if (n != null && keyInRange(n.getKey()))
				return n;
			return null;
		}

		public K higherKey(K key) {
			K found = TreeMap.this.higherKey(key);
			if (keyInRange(found))
				return found;
			else
				return null;
		}

		public Entry<K, V> lastEntry() {
			return lowerEntry(maxKey);
		}

		public K lastKey() {
			Entry<K, V> e = lastEntry();
			if (e == null)
				throw new NoSuchElementException();
			return e.getKey();
		}

		public Entry<K, V> lowerEntry(K key) {
			Entry<K, V> n = TreeMap.this.lowerEntry(key);
			if (n != null && keyInRange(n.getKey()))
				return n;
			return null;
		}

		public K lowerKey(K key) {
			K found = TreeMap.this.lowerKey(key);
			if (keyInRange(found))
				return found;
			else
				return null;
		}

		public NavigableSet<K> navigableKeySet() {
			if (this.nKeys == null)
				// Create an AbstractSet with custom implementations of those
				// methods
				// that can be overriden easily and efficiently.
				this.nKeys = new SubMap.NavigableKeySet();
			return this.nKeys;
		}

		public Entry<K, V> pollFirstEntry() {
			Entry<K, V> e = firstEntry();
			if (e != null)
				removeNode((Node<K, V>) e);
			return e;
		}

		public Entry<K, V> pollLastEntry() {
			Entry<K, V> e = lastEntry();
			if (e != null)
				removeNode((Node<K, V>) e);
			return e;
		}

		public V put(K key, V value) {
			if (!keyInRange(key))
				throw new IllegalArgumentException("Key outside range");
			return TreeMap.this.put(key, value);
		}

		public V remove(Object key) {
			if (keyInRange((K) key))
				return TreeMap.this.remove(key);
			return null;
		}

		public int size() {
			Node node = lowestGreaterThan(minKey, true);
			Node max = lowestGreaterThan(maxKey, false);
			int count = 0;
			while (node != max) {
				count++;
				node = successor(node);
			}
			return count;
		}

		public SortedMap<K, V> subMap(K fromKey, K toKey) {
			return subMap(fromKey, true, toKey, false);
		}

		public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive,
				K toKey, boolean toInclusive) {
			if (!keyInRange(fromKey) || !keyInRange(toKey))
				throw new IllegalArgumentException("key outside range");
			return new SubMap(fromInclusive ? fromKey
					: successor(getNode(fromKey)).key,
					toInclusive ? successor(getNode(toKey)).key : toKey);
		}

		public SortedMap<K, V> tailMap(K fromKey) {
			return tailMap(fromKey, true);
		}

		public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) {
			if (!keyInRange(fromKey))
				throw new IllegalArgumentException("key outside range");
			return new SubMap(inclusive ? fromKey
					: successor(getNode(fromKey)).key, maxKey);
		}

		public Collection<V> values() {
			if (this.values == null)
				// Create an AbstractCollection with custom implementations of
				// those
				// methods that can be overriden easily and efficiently.
				this.values = new AbstractCollection() {
					public int size() {
						return SubMap.this.size();
					}

					public Iterator<V> iterator() {
						Node first = lowestGreaterThan(minKey, true);
						Node max = lowestGreaterThan(maxKey, false);
						return new TreeIterator(VALUES, first, max);
					}

					public void clear() {
						SubMap.this.clear();
					}
				};
			return this.values;
		}

		private class KeySet extends AbstractSet<K> {
			public int size() {
				return SubMap.this.size();
			}

			public Iterator<K> iterator() {
				Node first = lowestGreaterThan(minKey, true);
				Node max = lowestGreaterThan(maxKey, false);
				return new TreeIterator(KEYS, first, max);
			}

			public void clear() {
				SubMap.this.clear();
			}

			public boolean contains(Object o) {
				if (!keyInRange((K) o))
					return false;
				return getNode((K) o) != nil;
			}

			public boolean remove(Object o) {
				if (!keyInRange((K) o))
					return false;
				Node n = getNode((K) o);
				if (n != nil) {
					removeNode(n);
					return true;
				}
				return false;
			}

		} // class SubMap.KeySet

		private final class NavigableKeySet extends KeySet implements
				NavigableSet<K> {

			public K ceiling(K k) {
				return SubMap.this.ceilingKey(k);
			}

			public Comparator<? super K> comparator() {
				return comparator;
			}

			public Iterator<K> descendingIterator() {
				return descendingSet().iterator();
			}

			public NavigableSet<K> descendingSet() {
				return new DescendingSet(this);
			}

			public K first() {
				return SubMap.this.firstKey();
			}

			public K floor(K k) {
				return SubMap.this.floorKey(k);
			}

			public SortedSet<K> headSet(K to) {
				return headSet(to, false);
			}

			public NavigableSet<K> headSet(K to, boolean inclusive) {
				return SubMap.this.headMap(to, inclusive).navigableKeySet();
			}

			public K higher(K k) {
				return SubMap.this.higherKey(k);
			}

			public K last() {
				return SubMap.this.lastKey();
			}

			public K lower(K k) {
				return SubMap.this.lowerKey(k);
			}

			public K pollFirst() {
				return SubMap.this.pollFirstEntry().getKey();
			}

			public K pollLast() {
				return SubMap.this.pollLastEntry().getKey();
			}

			public SortedSet<K> subSet(K from, K to) {
				return subSet(from, true, to, false);
			}

			public NavigableSet<K> subSet(K from, boolean fromInclusive, K to,
					boolean toInclusive) {
				return SubMap.this.subMap(from, fromInclusive, to, toInclusive)
						.navigableKeySet();
			}

			public SortedSet<K> tailSet(K from) {
				return tailSet(from, true);
			}

			public NavigableSet<K> tailSet(K from, boolean inclusive) {
				return SubMap.this.tailMap(from, inclusive).navigableKeySet();
			}

		} // class SubMap.NavigableKeySet

		/**
		 * Implementation of {@link #entrySet()}.
		 */
		private class EntrySet extends AbstractSet<Entry<K, V>> {

			public int size() {
				return SubMap.this.size();
			}

			public Iterator<Map.Entry<K, V>> iterator() {
				Node first = lowestGreaterThan(minKey, true);
				Node max = lowestGreaterThan(maxKey, false);
				return new TreeIterator(ENTRIES, first, max);
			}

			public void clear() {
				SubMap.this.clear();
			}

			public boolean contains(Object o) {
				if (!(o instanceof Map.Entry))
					return false;
				Map.Entry<K, V> me = (Map.Entry<K, V>) o;
				K key = me.getKey();
				if (!keyInRange(key))
					return false;
				Node<K, V> n = getNode(key);
				return n != nil && AbstractSet.equals(me.getValue(), n.value);
			}

			public boolean remove(Object o) {
				if (!(o instanceof Map.Entry))
					return false;
				Map.Entry<K, V> me = (Map.Entry<K, V>) o;
				K key = me.getKey();
				if (!keyInRange(key))
					return false;
				Node<K, V> n = getNode(key);
				if (n != nil && AbstractSet.equals(me.getValue(), n.value)) {
					removeNode(n);
					return true;
				}
				return false;
			}
		} // class SubMap.EntrySet

		private final class NavigableEntrySet extends EntrySet implements
				NavigableSet<Entry<K, V>> {

			public Entry<K, V> ceiling(Entry<K, V> e) {
				return SubMap.this.ceilingEntry(e.getKey());
			}

			public Comparator<? super Entry<K, V>> comparator() {
				return new Comparator<Entry<K, V>>() {
					public int compare(Entry<K, V> t1, Entry<K, V> t2) {
						return comparator.compare(t1.getKey(), t2.getKey());
					}
				};
			}

			public Iterator<Entry<K, V>> descendingIterator() {
				return descendingSet().iterator();
			}

			public NavigableSet<Entry<K, V>> descendingSet() {
				return new DescendingSet(this);
			}

			public Entry<K, V> first() {
				return SubMap.this.firstEntry();
			}

			public Entry<K, V> floor(Entry<K, V> e) {
				return SubMap.this.floorEntry(e.getKey());
			}

			public SortedSet<Entry<K, V>> headSet(Entry<K, V> to) {
				return headSet(to, false);
			}

			public NavigableSet<Entry<K, V>> headSet(Entry<K, V> to,
					boolean inclusive) {
				return (NavigableSet<Entry<K, V>>) SubMap.this.headMap(
						to.getKey(), inclusive).entrySet();
			}

			public Entry<K, V> higher(Entry<K, V> e) {
				return SubMap.this.higherEntry(e.getKey());
			}

			public Entry<K, V> last() {
				return SubMap.this.lastEntry();
			}

			public Entry<K, V> lower(Entry<K, V> e) {
				return SubMap.this.lowerEntry(e.getKey());
			}

			public Entry<K, V> pollFirst() {
				return SubMap.this.pollFirstEntry();
			}

			public Entry<K, V> pollLast() {
				return SubMap.this.pollLastEntry();
			}

			public SortedSet<Entry<K, V>> subSet(Entry<K, V> from,
					Entry<K, V> to) {
				return subSet(from, true, to, false);
			}

			public NavigableSet<Entry<K, V>> subSet(Entry<K, V> from,
					boolean fromInclusive, Entry<K, V> to, boolean toInclusive) {
				return (NavigableSet<Entry<K, V>>) SubMap.this.subMap(
						from.getKey(), fromInclusive, to.getKey(), toInclusive)
						.entrySet();
			}

			public SortedSet<Entry<K, V>> tailSet(Entry<K, V> from) {
				return tailSet(from, true);
			}

			public NavigableSet<Entry<K, V>> tailSet(Entry<K, V> from,
					boolean inclusive) {
				return (NavigableSet<Entry<K, V>>) SubMap.this.tailMap(
						from.getKey(), inclusive).navigableKeySet();
			}

		} // class SubMap.NavigableEntrySet

	} // class SubMap

	/**
	 * Returns the entry associated with the least or lowest key that is greater
	 * than or equal to the specified key, or <code>null</code> if there is no
	 * such key.
	 * 
	 * @param key
	 *            the key relative to the returned entry.
	 * @return the entry with the least key greater than or equal to the given
	 *         key, or <code>null</code> if there is no such key.
	 * @throws ClassCastException
	 *             if the specified key can not be compared with those in the
	 *             map.
	 * @throws NullPointerException
	 *             if the key is <code>null</code> and this map either uses
	 *             natural ordering or a comparator that does not permit null
	 *             keys.
	 * @since 1.6
	 */
	public Entry<K, V> ceilingEntry(K key) {
		Node<K, V> n = lowestGreaterThan(key, false);
		return (n == nil) ? null : n;
	}

	/**
	 * Returns the the least or lowest key that is greater than or equal to the
	 * specified key, or <code>null</code> if there is no such key.
	 * 
	 * @param key
	 *            the key relative to the returned entry.
	 * @return the least key greater than or equal to the given key, or
	 *         <code>null</code> if there is no such key.
	 * @throws ClassCastException
	 *             if the specified key can not be compared with those in the
	 *             map.
	 * @throws NullPointerException
	 *             if the key is <code>null</code> and this map either uses
	 *             natural ordering or a comparator that does not permit null
	 *             keys.
	 * @since 1.6
	 */
	public K ceilingKey(K key) {
		Entry<K, V> e = ceilingEntry(key);
		return (e == null) ? null : e.getKey();
	}

	/**
	 * Returns a reverse ordered {@link NavigableSet} view of this map's keys.
	 * The set is backed by the {@link TreeMap}, so changes in one show up in
	 * the other. The set supports element removal, but not element addition.
	 * 
	 * @return a reverse ordered set view of the keys.
	 * @since 1.6
	 * @see #descendingMap()
	 */
	public NavigableSet<K> descendingKeySet() {
		return descendingMap().navigableKeySet();
	}

	/**
	 * Returns a view of the map in reverse order. The descending map is backed
	 * by the original map, so that changes affect both maps. Any changes
	 * occurring to either map while an iteration is taking place (with the
	 * exception of a {@link Iterator#remove()} operation) result in undefined
	 * behaviour from the iteration. The ordering of the descending map is the
	 * same as for a map with a {@link Comparator} given by
	 * {@link Collections#reverseOrder()}, and calling {@link #descendingMap()}
	 * on the descending map itself results in a view equivalent to the original
	 * map.
	 * 
	 * @return a reverse order view of the map.
	 * @since 1.6
	 */
	public NavigableMap<K, V> descendingMap() {
		if (descendingMap == null)
			descendingMap = new DescendingMap<K, V>(this);
		return descendingMap;
	}

	/**
	 * Returns the entry associated with the least or lowest key in the map, or
	 * <code>null</code> if the map is empty.
	 * 
	 * @return the lowest entry, or <code>null</code> if the map is empty.
	 * @since 1.6
	 */
	public Entry<K, V> firstEntry() {
		Node<K, V> n = firstNode();
		return (n == nil) ? null : n;
	}

	/**
	 * Returns the entry associated with the greatest or highest key that is
	 * less than or equal to the specified key, or <code>null</code> if there is
	 * no such key.
	 * 
	 * @param key
	 *            the key relative to the returned entry.
	 * @return the entry with the greatest key less than or equal to the given
	 *         key, or <code>null</code> if there is no such key.
	 * @throws ClassCastException
	 *             if the specified key can not be compared with those in the
	 *             map.
	 * @throws NullPointerException
	 *             if the key is <code>null</code> and this map either uses
	 *             natural ordering or a comparator that does not permit null
	 *             keys.
	 * @since 1.6
	 */
	public Entry<K, V> floorEntry(K key) {
		Node<K, V> n = highestLessThan(key, true);
		return (n == nil) ? null : n;
	}

	/**
	 * Returns the the greatest or highest key that is less than or equal to the
	 * specified key, or <code>null</code> if there is no such key.
	 * 
	 * @param key
	 *            the key relative to the returned entry.
	 * @return the greatest key less than or equal to the given key, or
	 *         <code>null</code> if there is no such key.
	 * @throws ClassCastException
	 *             if the specified key can not be compared with those in the
	 *             map.
	 * @throws NullPointerException
	 *             if the key is <code>null</code> and this map either uses
	 *             natural ordering or a comparator that does not permit null
	 *             keys.
	 * @since 1.6
	 */
	public K floorKey(K key) {
		Entry<K, V> e = floorEntry(key);
		return (e == null) ? null : e.getKey();
	}

	/**
	 * Returns the entry associated with the least or lowest key that is
	 * strictly greater than the specified key, or <code>null</code> if there is
	 * no such key.
	 * 
	 * @param key
	 *            the key relative to the returned entry.
	 * @return the entry with the least key greater than the given key, or
	 *         <code>null</code> if there is no such key.
	 * @throws ClassCastException
	 *             if the specified key can not be compared with those in the
	 *             map.
	 * @throws NullPointerException
	 *             if the key is <code>null</code> and this map either uses
	 *             natural ordering or a comparator that does not permit null
	 *             keys.
	 * @since 1.6
	 */
	public Entry<K, V> higherEntry(K key) {
		Node<K, V> n = lowestGreaterThan(key, false, false);
		return (n == nil) ? null : n;
	}

	/**
	 * Returns the the least or lowest key that is strictly greater than the
	 * specified key, or <code>null</code> if there is no such key.
	 * 
	 * @param key
	 *            the key relative to the returned entry.
	 * @return the least key greater than the given key, or <code>null</code> if
	 *         there is no such key.
	 * @throws ClassCastException
	 *             if the specified key can not be compared with those in the
	 *             map.
	 * @throws NullPointerException
	 *             if the key is <code>null</code> and this map either uses
	 *             natural ordering or a comparator that does not permit null
	 *             keys.
	 * @since 1.6
	 */
	public K higherKey(K key) {
		Entry<K, V> e = higherEntry(key);
		return (e == null) ? null : e.getKey();
	}

	/**
	 * Returns the entry associated with the greatest or highest key in the map,
	 * or <code>null</code> if the map is empty.
	 * 
	 * @return the highest entry, or <code>null</code> if the map is empty.
	 * @since 1.6
	 */
	public Entry<K, V> lastEntry() {
		Node<K, V> n = lastNode();
		return (n == nil) ? null : n;
	}

	/**
	 * Returns the entry associated with the greatest or highest key that is
	 * strictly less than the specified key, or <code>null</code> if there is no
	 * such key.
	 * 
	 * @param key
	 *            the key relative to the returned entry.
	 * @return the entry with the greatest key less than the given key, or
	 *         <code>null</code> if there is no such key.
	 * @throws ClassCastException
	 *             if the specified key can not be compared with those in the
	 *             map.
	 * @throws NullPointerException
	 *             if the key is <code>null</code> and this map either uses
	 *             natural ordering or a comparator that does not permit null
	 *             keys.
	 * @since 1.6
	 */
	public Entry<K, V> lowerEntry(K key) {
		Node<K, V> n = highestLessThan(key);
		return (n == nil) ? null : n;
	}

	/**
	 * Returns the the greatest or highest key that is strictly less than the
	 * specified key, or <code>null</code> if there is no such key.
	 * 
	 * @param key
	 *            the key relative to the returned entry.
	 * @return the greatest key less than the given key, or <code>null</code> if
	 *         there is no such key.
	 * @throws ClassCastException
	 *             if the specified key can not be compared with those in the
	 *             map.
	 * @throws NullPointerException
	 *             if the key is <code>null</code> and this map either uses
	 *             natural ordering or a comparator that does not permit null
	 *             keys.
	 * @since 1.6
	 */
	public K lowerKey(K key) {
		Entry<K, V> e = lowerEntry(key);
		return (e == null) ? null : e.getKey();
	}

	/**
	 * Returns a {@link NavigableSet} view of this map's keys. The set is backed
	 * by the {@link TreeMap}, so changes in one show up in the other. Any
	 * changes occurring to either while an iteration is taking place (with the
	 * exception of a {@link Iterator#remove()} operation) result in undefined
	 * behaviour from the iteration. The ordering The set supports element
	 * removal, but not element addition.
	 * 
	 * @return a {@link NavigableSet} view of the keys.
	 * @since 1.6
	 */
	public NavigableSet<K> navigableKeySet() {
		if (nKeys == null)
			nKeys = new NavigableKeySet();
		return nKeys;
	}

	/**
	 * Removes and returns the entry associated with the least or lowest key in
	 * the map, or <code>null</code> if the map is empty.
	 * 
	 * @return the removed first entry, or <code>null</code> if the map is
	 *         empty.
	 * @since 1.6
	 */
	public Entry<K, V> pollFirstEntry() {
		Entry<K, V> e = firstEntry();
		if (e != null)
			removeNode((Node<K, V>) e);
		return e;
	}

	/**
	 * Removes and returns the entry associated with the greatest or highest key
	 * in the map, or <code>null</code> if the map is empty.
	 * 
	 * @return the removed last entry, or <code>null</code> if the map is empty.
	 * @since 1.6
	 */
	public Entry<K, V> pollLastEntry() {
		Entry<K, V> e = lastEntry();
		if (e != null)
			removeNode((Node<K, V>) e);
		return e;
	}

	/**
	 * Implementation of {@link #descendingMap()} and associated derivatives.
	 * This class provides a view of the original backing map in reverse order,
	 * and throws {@link IllegalArgumentException} for attempts to access beyond
	 * that range.
	 * 
	 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
	 */
	private static final class DescendingMap<DK, DV> implements
			NavigableMap<DK, DV> {

		/**
		 * The cache for {@link #entrySet()}.
		 */
		private Set<Map.Entry<DK, DV>> entries;

		/**
		 * The cache for {@link #keySet()}.
		 */
		private Set<DK> keys;

		/**
		 * The cache for {@link #navigableKeySet()}.
		 */
		private NavigableSet<DK> nKeys;

		/**
		 * The cache for {@link #values()}.
		 */
		private Collection<DV> values;

		/**
		 * The backing {@link NavigableMap}.
		 */
		private NavigableMap<DK, DV> map;

		/**
		 * Create a {@link DescendingMap} around the specified map.
		 * 
		 * @param map
		 *            the map to wrap.
		 */
		public DescendingMap(NavigableMap<DK, DV> map) {
			this.map = map;
		}

		public Map.Entry<DK, DV> ceilingEntry(DK key) {
			return map.floorEntry(key);
		}

		public DK ceilingKey(DK key) {
			return map.floorKey(key);
		}

		public void clear() {
			map.clear();
		}

		public Comparator<? super DK> comparator() {
			return Collections.reverseOrder(map.comparator());
		}

		public boolean containsKey(Object o) {
			return map.containsKey(o);
		}

		public boolean containsValue(Object o) {
			return map.containsValue(o);
		}

		public NavigableSet<DK> descendingKeySet() {
			return descendingMap().navigableKeySet();
		}

		public NavigableMap<DK, DV> descendingMap() {
			return map;
		}

		public Set<Entry<DK, DV>> entrySet() {
			if (entries == null)
				entries = new DescendingSet<Entry<DK, DV>>(
						(NavigableSet<Entry<DK, DV>>) map.entrySet());
			return entries;
		}

		public boolean equals(Object o) {
			return map.equals(o);
		}

		public Entry<DK, DV> firstEntry() {
			return map.lastEntry();
		}

		public DK firstKey() {
			return map.lastKey();
		}

		public Entry<DK, DV> floorEntry(DK key) {
			return map.ceilingEntry(key);
		}

		public DK floorKey(DK key) {
			return map.ceilingKey(key);
		}

		public DV get(Object key) {
			return map.get(key);
		}

		public int hashCode() {
			return map.hashCode();
		}

		public SortedMap<DK, DV> headMap(DK toKey) {
			return headMap(toKey, false);
		}

		public NavigableMap<DK, DV> headMap(DK toKey, boolean inclusive) {
			return new DescendingMap(map.tailMap(toKey, inclusive));
		}

		public Entry<DK, DV> higherEntry(DK key) {
			return map.lowerEntry(key);
		}

		public DK higherKey(DK key) {
			return map.lowerKey(key);
		}

		public Set<DK> keySet() {
			if (keys == null)
				keys = new DescendingSet<DK>(map.navigableKeySet());
			return keys;
		}

		public boolean isEmpty() {
			return map.isEmpty();
		}

		public Entry<DK, DV> lastEntry() {
			return map.firstEntry();
		}

		public DK lastKey() {
			return map.firstKey();
		}

		public Entry<DK, DV> lowerEntry(DK key) {
			return map.higherEntry(key);
		}

		public DK lowerKey(DK key) {
			return map.higherKey(key);
		}

		public NavigableSet<DK> navigableKeySet() {
			if (nKeys == null)
				nKeys = new DescendingSet<DK>(map.navigableKeySet());
			return nKeys;
		}

		public Entry<DK, DV> pollFirstEntry() {
			return pollLastEntry();
		}

		public Entry<DK, DV> pollLastEntry() {
			return pollFirstEntry();
		}

		public DV put(DK key, DV value) {
			return map.put(key, value);
		}

		public void putAll(Map<? extends DK, ? extends DV> m) {
			map.putAll(m);
		}

		public DV remove(Object key) {
			return map.remove(key);
		}

		public int size() {
			return map.size();
		}

		public SortedMap<DK, DV> subMap(DK fromKey, DK toKey) {
			return subMap(fromKey, true, toKey, false);
		}

		public NavigableMap<DK, DV> subMap(DK fromKey, boolean fromInclusive,
				DK toKey, boolean toInclusive) {
			return new DescendingMap(map.subMap(fromKey, fromInclusive, toKey,
					toInclusive));
		}

		public SortedMap<DK, DV> tailMap(DK fromKey) {
			return tailMap(fromKey, true);
		}

		public NavigableMap<DK, DV> tailMap(DK fromKey, boolean inclusive) {
			return new DescendingMap(map.headMap(fromKey, inclusive));
		}

		public String toString() {
			StringBuilder r = new StringBuilder("{");
			final Iterator<Entry<DK, DV>> it = entrySet().iterator();
			while (it.hasNext()) {
				final Entry<DK, DV> e = it.next();
				r.append(e.getKey());
				r.append('=');
				r.append(e.getValue());
				r.append(", ");
			}
			r.replace(r.length() - 2, r.length(), "}");
			return r.toString();
		}

		public Collection<DV> values() {
			if (values == null)
				// Create an AbstractCollection with custom implementations of
				// those
				// methods that can be overriden easily and efficiently.
				values = new AbstractCollection() {
					public int size() {
						return size();
					}

					public Iterator<DV> iterator() {
						return new Iterator<DV>() {
							/** The last Entry returned by a next() call. */
							private Entry<DK, DV> last;

							/**
							 * The next entry that should be returned by next().
							 */
							private Entry<DK, DV> next = firstEntry();

							public boolean hasNext() {
								return next != null;
							}

							public DV next() {
								if (next == null)
									throw new NoSuchElementException();
								last = next;
								next = higherEntry(last.getKey());

								return last.getValue();
							}

							public void remove() {
								if (last == null)
									throw new IllegalStateException();

								DescendingMap.this.remove(last.getKey());
								last = null;
							}
						};
					}

					public void clear() {
						clear();
					}
				};
			return values;
		}

	} // class DescendingMap

	/**
	 * Implementation of {@link #keySet()}.
	 */
	private class KeySet extends AbstractSet<K> {

		public int size() {
			return size;
		}

		public Iterator<K> iterator() {
			return new TreeIterator(KEYS);
		}

		public void clear() {
			TreeMap.this.clear();
		}

		public boolean contains(Object o) {
			return containsKey(o);
		}

		public boolean remove(Object key) {
			Node<K, V> n = getNode((K) key);
			if (n == nil)
				return false;
			removeNode(n);
			return true;
		}
	} // class KeySet

	/**
	 * Implementation of {@link #navigableKeySet()}.
	 * 
	 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
	 */
	private final class NavigableKeySet extends KeySet implements
			NavigableSet<K> {

		public K ceiling(K k) {
			return ceilingKey(k);
		}

		public Comparator<? super K> comparator() {
			return comparator;
		}

		public Iterator<K> descendingIterator() {
			return descendingSet().iterator();
		}

		public NavigableSet<K> descendingSet() {
			return new DescendingSet<K>(this);
		}

		public K first() {
			return firstKey();
		}

		public K floor(K k) {
			return floorKey(k);
		}

		public SortedSet<K> headSet(K to) {
			return headSet(to, false);
		}

		public NavigableSet<K> headSet(K to, boolean inclusive) {
			return headMap(to, inclusive).navigableKeySet();
		}

		public K higher(K k) {
			return higherKey(k);
		}

		public K last() {
			return lastKey();
		}

		public K lower(K k) {
			return lowerKey(k);
		}

		public K pollFirst() {
			return pollFirstEntry().getKey();
		}

		public K pollLast() {
			return pollLastEntry().getKey();
		}

		public SortedSet<K> subSet(K from, K to) {
			return subSet(from, true, to, false);
		}

		public NavigableSet<K> subSet(K from, boolean fromInclusive, K to,
				boolean toInclusive) {
			return subMap(from, fromInclusive, to, toInclusive)
					.navigableKeySet();
		}

		public SortedSet<K> tailSet(K from) {
			return tailSet(from, true);
		}

		public NavigableSet<K> tailSet(K from, boolean inclusive) {
			return tailMap(from, inclusive).navigableKeySet();
		}

	} // class NavigableKeySet

	/**
	 * Implementation of {@link #descendingSet()} and associated derivatives.
	 * This class provides a view of the original backing set in reverse order,
	 * and throws {@link IllegalArgumentException} for attempts to access beyond
	 * that range.
	 * 
	 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
	 */
	private static final class DescendingSet<D> implements NavigableSet<D> {

		/**
		 * The backing {@link NavigableSet}.
		 */
		private NavigableSet<D> set;

		/**
		 * Create a {@link DescendingSet} around the specified set.
		 * 
		 * @param map
		 *            the set to wrap.
		 */
		public DescendingSet(NavigableSet<D> set) {
			this.set = set;
		}

		public boolean add(D e) {
			return set.add(e);
		}

		public boolean addAll(Collection<? extends D> c) {
			return set.addAll(c);
		}

		public D ceiling(D e) {
			return set.floor(e);
		}

		public void clear() {
			set.clear();
		}

		public Comparator<? super D> comparator() {
			return Collections.reverseOrder(set.comparator());
		}

		public boolean contains(Object o) {
			return set.contains(o);
		}

		public boolean containsAll(Collection<?> c) {
			return set.containsAll(c);
		}

		public Iterator<D> descendingIterator() {
			return descendingSet().iterator();
		}

		public NavigableSet<D> descendingSet() {
			return set;
		}

		public boolean equals(Object o) {
			return set.equals(o);
		}

		public D first() {
			return set.last();
		}

		public D floor(D e) {
			return set.ceiling(e);
		}

		public int hashCode() {
			return set.hashCode();
		}

		public SortedSet<D> headSet(D to) {
			return headSet(to, false);
		}

		public NavigableSet<D> headSet(D to, boolean inclusive) {
			return new DescendingSet(set.tailSet(to, inclusive));
		}

		public D higher(D e) {
			return set.lower(e);
		}

		public boolean isEmpty() {
			return set.isEmpty();
		}

		public Iterator<D> iterator() {
			return new Iterator<D>() {

				/** The last element returned by a next() call. */
				private D last;

				/** The next element that should be returned by next(). */
				private D next = first();

				public boolean hasNext() {
					return next != null;
				}

				public D next() {
					if (next == null)
						throw new NoSuchElementException();
					last = next;
					next = higher(last);

					return last;
				}

				public void remove() {
					if (last == null)
						throw new IllegalStateException();

					DescendingSet.this.remove(last);
					last = null;
				}
			};
		}

		public D last() {
			return set.first();
		}

		public D lower(D e) {
			return set.higher(e);
		}

		public D pollFirst() {
			return set.pollLast();
		}

		public D pollLast() {
			return set.pollFirst();
		}

		public boolean remove(Object o) {
			return set.remove(o);
		}

		public boolean removeAll(Collection<?> c) {
			return set.removeAll(c);
		}

		public boolean retainAll(Collection<?> c) {
			return set.retainAll(c);
		}

		public int size() {
			return set.size();
		}

		public SortedSet<D> subSet(D from, D to) {
			return subSet(from, true, to, false);
		}

		public NavigableSet<D> subSet(D from, boolean fromInclusive, D to,
				boolean toInclusive) {
			return new DescendingSet(set.subSet(from, fromInclusive, to,
					toInclusive));
		}

		public SortedSet<D> tailSet(D from) {
			return tailSet(from, true);
		}

		public NavigableSet<D> tailSet(D from, boolean inclusive) {
			return new DescendingSet(set.headSet(from, inclusive));
		}

		public Object[] toArray() {
			D[] array = (D[]) set.toArray();
			Arrays.sort(array, comparator());
			return array;
		}

		public <T> T[] toArray(T[] a) {
			T[] array = set.toArray(a);
			Arrays.sort(array, (Comparator<? super T>) comparator());
			return array;
		}

		public String toString() {
			StringBuilder r = new StringBuilder("[");
			final Iterator<D> it = iterator();
			while (it.hasNext()) {
				final D o = it.next();
				if (o == this)
					r.append("<this>");
				else
					r.append(o);
				r.append(", ");
			}
			r.replace(r.length() - 2, r.length(), "]");
			return r.toString();
		}

	} // class DescendingSet

	private class EntrySet extends AbstractSet<Entry<K, V>> {
		public int size() {
			return size;
		}

		public Iterator<Map.Entry<K, V>> iterator() {
			return new TreeIterator(ENTRIES);
		}

		public void clear() {
			TreeMap.this.clear();
		}

		public boolean contains(Object o) {
			if (!(o instanceof Map.Entry))
				return false;
			Map.Entry<K, V> me = (Map.Entry<K, V>) o;
			Node<K, V> n = getNode(me.getKey());
			return n != nil && AbstractSet.equals(me.getValue(), n.value);
		}

		public boolean remove(Object o) {
			if (!(o instanceof Map.Entry))
				return false;
			Map.Entry<K, V> me = (Map.Entry<K, V>) o;
			Node<K, V> n = getNode(me.getKey());
			if (n != nil && AbstractSet.equals(me.getValue(), n.value)) {
				removeNode(n);
				return true;
			}
			return false;
		}
	}

	private final class NavigableEntrySet extends EntrySet implements
			NavigableSet<Entry<K, V>> {

		public Entry<K, V> ceiling(Entry<K, V> e) {
			return ceilingEntry(e.getKey());
		}

		public Comparator<? super Entry<K, V>> comparator() {
			return new Comparator<Entry<K, V>>() {
				public int compare(Entry<K, V> t1, Entry<K, V> t2) {
					return comparator.compare(t1.getKey(), t2.getKey());
				}
			};
		}

		public Iterator<Entry<K, V>> descendingIterator() {
			return descendingSet().iterator();
		}

		public NavigableSet<Entry<K, V>> descendingSet() {
			return new DescendingSet(this);
		}

		public Entry<K, V> first() {
			return firstEntry();
		}

		public Entry<K, V> floor(Entry<K, V> e) {
			return floorEntry(e.getKey());
		}

		public SortedSet<Entry<K, V>> headSet(Entry<K, V> to) {
			return headSet(to, false);
		}

		public NavigableSet<Entry<K, V>> headSet(Entry<K, V> to,
				boolean inclusive) {
			return (NavigableSet<Entry<K, V>>) headMap(to.getKey(), inclusive)
					.entrySet();
		}

		public Entry<K, V> higher(Entry<K, V> e) {
			return higherEntry(e.getKey());
		}

		public Entry<K, V> last() {
			return lastEntry();
		}

		public Entry<K, V> lower(Entry<K, V> e) {
			return lowerEntry(e.getKey());
		}

		public Entry<K, V> pollFirst() {
			return pollFirstEntry();
		}

		public Entry<K, V> pollLast() {
			return pollLastEntry();
		}

		public SortedSet<Entry<K, V>> subSet(Entry<K, V> from, Entry<K, V> to) {
			return subSet(from, true, to, false);
		}

		public NavigableSet<Entry<K, V>> subSet(Entry<K, V> from,
				boolean fromInclusive, Entry<K, V> to, boolean toInclusive) {
			return (NavigableSet<Entry<K, V>>) subMap(from.getKey(),
					fromInclusive, to.getKey(), toInclusive).entrySet();
		}

		public SortedSet<Entry<K, V>> tailSet(Entry<K, V> from) {
			return tailSet(from, true);
		}

		public NavigableSet<Entry<K, V>> tailSet(Entry<K, V> from,
				boolean inclusive) {
			return (NavigableSet<Entry<K, V>>) tailMap(from.getKey(), inclusive)
					.navigableKeySet();
		}

	} // class NavigableEntrySet

} // class TreeMap
